import collections
import bisect

class TimeMap(object):

    def __init__(self):
        self.d_time = collections.defaultdict(list)
        self.d_value = collections.defaultdict(list)

    def set(self, key, value, timestamp):
        """
        :type key: str
        :type value: str
        :type timestamp: int
        :rtype: None
        """
        self.d_time[key].append(timestamp)
        self.d_value[key].append(value)

    def get(self, key, timestamp):
        index = bisect.bisect_right(self.d_time[key], timestamp)
        if index == 0:
            return ''
        else:
            return self.d_value[key][index - 1]

